package com.li.algorithm.leetcode.hot100;
public class Test24 {
    public boolean isPalindrome(ListNode head) {
        int[] arr = new int[100001];
        ListNode p = head;
        int len = 0;
        while (p != null) {
            arr[len] = p.val;
            len++;
            p = p.next;
        }
        boolean flag = true;
        int i = 0, j = len - 1;
        while (i < j) {
            if (arr[i] != arr[j]) {
                flag = false;
                break;
            }
            i++;
            j--;
        }
        return flag;
    }


    /**
     * 方法2：空间复杂度为 O(1) 的算法
     */
    public boolean isPalindrome2(ListNode head) {
        //TODO: 将链表平分两段，第二段反转
        ListNode firstHalfEnd = getHalfList(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd);

        //TODO: 将第一段和反转后的第二段对比
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        //TODO: 恢复反转后的第二段
        firstHalfEnd.next = reverseList(secondHalfStart);
        return true;
    }


    /**
     * 通过快慢指针获取链表中间位置
     */
    public ListNode getHalfList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode p = head;
        ListNode pre = null;
        ListNode next;

        while (p != null) {
            next = p.next;
            p.next = pre;
            pre = p;
            p = next;
        }
        return pre;
    }



    public static void main(String[] args) {
        int[] arr = {1,2};
        ListNode head = new ListNode(arr[0]);
        ListNode pre = head;
        for (int i = 1; i < arr.length; i++) {
            ListNode node = new ListNode(arr[i]);
            pre.next = node;
            pre = node;
        }
        Test24 test24 = new Test24();
        System.out.println(test24.isPalindrome2(head));

    }

}
